package com.vic.datastructure.sort.insert;

/**
 * @author victor
 */
public class InsertSort1 {

    public static void main(String[] args) {
        int [] arr = {5, 2, 32, 12, 83, 12, 24, 45};

        int i, j;
        for(i = 2; i <= arr.length; i++) {
            if(arr[i] < arr[i-1]) {
                // 复制为哨兵
                arr[0] = arr[i];

                for(j = i - 1; arr[0] < arr[j]; --j) {
                    arr[j+1] = arr[j];
                }

                arr[j+1] = arr[0];
            }
        }

        printArr(arr);

    }

    private static void printArr(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
